/*
 * @Author: lei
 * @Date: 2021-08-06 11:42:13
 * @LastEditTime: 2021-08-06 12:03:22
 * @LastEditors: Please set LastEditors
 * @Description: 选择排序
 * @FilePath: /code/selection_sort.cpp
 */

#include <iostream>
#include <vector>
using namespace std;
void selection_sort1(vector<int>& v)
{
    int index;
    int n=v.size();
    for(int i=0;i<n;i++)
    {
        index=i;
        for(int j=i+1;j<n;j++)
        {
            if(v[j]<v[index])
            {
                index=j;
            }
        }
        swap(v[i],v[index]);
    }
}

void selection_sort2(vector<int>& arr) {
    int minIndex, maxIndex;
    // i 只需要遍历一半
    int n=arr.size();
    for (int i = 0; i < n / 2; i++) {
        minIndex = i;
        maxIndex = i;
        for (int j = i + 1; j < n - i; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                // 记录最大值的下标
                maxIndex = j;
            }
        }
        // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
        if (minIndex == maxIndex) break;
        // 将最小元素交换至首位
        swap(arr[i],arr[minIndex]);
        // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
        if (maxIndex == i) maxIndex = minIndex;
        // 将最大元素交换至末尾
        int lastIndex = n  - 1 - i;
        swap(arr[lastIndex],arr[maxIndex]);
    }
}

int main()
{
    vector<int> v{1,4,3,7,5,8,9,2,1};
    for(auto vv:v)
        cout<<vv<<" ";
    cout<<endl;
    //selection_sort1(v);
    selection_sort2(v);
    for(auto vv:v)
        cout<<vv<<" ";
    cout<<endl;
    return 0;
}